#include <stdio.h>
#include <vector>
#include <cmath>

//筛选出从2到sqrt(maxnumber)的质数
std::vector<int> sieve(int max_num) {
    std::vector<int> primes;
    std::vector<bool> is_prime(max_num + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= max_num; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= max_num; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return primes;
}

int operationtime(int n, const std::vector<int>& primes) {
    int time = 0;
    
    while (n%2!=0){
        int tag=1;
        for (int prime : primes) {
            if (prime*prime > n){
                break;
            }
            if (n % prime == 0) {
                //printf("%d\n",prime);
                n -= prime;
                time++;
                tag=0;
                break;
            }

        }
        
        if (tag==1){//表示处理到最后一步为一个素数
            time++;
            break;
        }
    }
    if (n%2==0){time+=(n/2);}
    return time;
}

int main() {
    int num;
    scanf("%d", &num);
    std::vector<int> results;
    for (int i = 0; i < num; i++) {
        int n;
        scanf("%d", &n);
        results.push_back(n);
    }
    int maxnumber=results[0];
    for (int n : results){
        maxnumber = std::max(maxnumber, n);
    }
    maxnumber=(int)sqrt(maxnumber);
    std::vector<int> primes = sieve(maxnumber);

    std::vector<int> result2(num);
    for (int i = 0; i < num; i++) {
        result2[i] = operationtime(results[i], primes);
    }

    for (int i = 0; i < num; i++) {
        printf("%d\n", result2[i]);
    }

    return 0;
}